package 牛客_面试必刷.Month07.day08;

import java.util.ArrayList;

public class 合并K个升序链表 {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists.size() == 0)  return null;
        ListNode t1 = lists.get(0);
        for (int i = 1; i < lists.size(); i++) {
            t1 = solve(t1,lists.get(i));
        }
        return t1;
    }

    public ListNode solve(ListNode head1,ListNode head2){
        ListNode head = new ListNode(-1);
        ListNode myhead = head;
        while(head1 != null && head2 != null){
            if(head1.val > head2.val){
                myhead.next = head2;
                head2 = head2.next;
            }else{
                myhead.next = head1;
                head1 = head1.next;
            }
            myhead = myhead.next;
        }
//         if(head1 == null) myhead.next = head2;
//         if(head2 == null) myhead.next = head1;
        myhead.next = (head1 == null) ?  head2 : head1;
        return head.next;
    }
}
